\documentclass[a4paper,10pt]{article}
\usepackage{amsmath, amssymb, graphicx, url}

\usepackage[pdftex]{hyperref}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=black,urlcolor=black}

\title{Assignment 3 - Traffic Simulation}
\author{Jannis Teunissen \and Florian Speelman}
\begin{document}
\maketitle
\section{Introduction - Model of a road network}
\begin{figure}
\begin{center}
\includegraphics[width=7cm]{roads.png}
\end{center}
\caption{The road network we studied. There are three intersections connected by two way roads, and each intersection is also connected to the `outside world'.
\label{fig:roadnetwork}}
\end{figure}
We studied a quite simple and small road network. It consists of three intersections with traffic lights connected by two-way roads, see figure \ref{fig:roadnetwork}.
At every intersection there is also a two-way road to the `outside world'. We can describe this small system as a queueing network by replacing the intersections and roads by queues, a simple version would for example be:
\begin{itemize}
\item Describe every traffic light as a queue with infinite capacity that has a single server. Service times are exponentially distributed around some constant mean.
\item Describe every road as a queue with infinite capacity that has multiple servers, the number of which depends on the road length. Service times are constant. 
\item The outside world acts by sending cars to the intersections, arrival times are exponentially distributed. When a car arrives at an intersection it can either go to one of the other two intersections or leave the system. The probability of going in a certain direction at an intersection is constant.
\end{itemize}
Of course this is far from realistic, but by keeping it so simple we can get analytical predictions for the steady state solutions. The next section discusses a special type of queueing networks: Jackson networks.

\section{Jackson networks}
A queueing network with $M$ nodes is called a Jackson network when it meets the following conditions
(following the notation of \cite{lenin}):\\
\\
New customers (in our case cars) join the system according to a Poisson process,
let's call the join rate $\lambda_0$. A car joins node $i$ with probability $p_{0i}$, giving the node the join rate $\lambda_0 p_{0i}$.\\
The service time at every node is exponentially distributed with rate $\mu_i$.\\
The type of service is First In First Out.\\
When a car leaves node $i$ it goes to node $j$ with probability $p_{ij}$ or leaves the network with probability $p_{i0} = 1 - \sum_{j=1}^M{p_{ij}}$.\\

Any node $i$ receives cars not just from outside, but also from other nodes. This gives
a total arrival rate, called $\lambda_i$, which is given by the set of equations:
\begin{equation}
\lambda_i = \lambda_0 p_{0i} + \sum_{j=1}^M{\lambda_j p_{ji}}\text{.}
\label{eq:flow}
\end{equation}
Using this we can also define the utilization $\rho_i = \frac{\lambda_i}{\mu_i}$. The utilization has to
be less than 1 for every node. Now if the
network meets all these conditions, Jackson's theorem states that the equilibrium state probability
distribution of the entire system is equal to the product of the individual queue equilibrium distributions.
Letting $X_i$ be the number of cars at node $i$, we can write it as
\begin{align*}
p_{n_1,\dots,n_M} &= P\{X_1 = n_1, X_2 = n_2, \dots, X_M = n_M\} = \prod_{i=1}^M{P_i\{X_i=n_i\}}\\
&= \prod_{i=1}^M{P_i(n_i)}\text{,}
\end{align*}
where $P_i(n_i)$ is called the marginal probability distribution of node $i$.
Jackson's theorem applies to queues with any amount of servers, M/M/m queues, 
but we will use a network with only M/M/1 nodes. For this type of queue 
the marginal probability distribution of each node is known, and
the total distribution is given by
\begin{equation}
p_{n_1,\dots,n_M} = \prod_{i=1}^M{\rho_i^{n_i} (1 - \rho_i)} \text{.}
\label{eq:p}
\end{equation}

The road network of figure \ref{fig:roadnetwork} can be modelled as a Jackson network consisting of three nodes, the intersections.
They have mean processing times $\mu_1$, $\mu_2$, and $\mu_3$. The total
rate of incoming cars is $\lambda_0$ and the intersections have a probability
of a new car coming there $p_{01}$, $p_{02}$, and $p_{03}$. The probability of going from node $i$ to node $j$ is given by $p_{ij}$.
%The probability of leaving the system is $\lambda_{10} = \lambda_{20} = \lambda_{30} = p_{out}$,
%and not leaving the system a car will randomly go to one of the other intersections.
%This means $p_{12} = p_{21} = p_{13} = p_{31} = p_{23} = p_{32} = \frac{1 - p_{out}}{2}$.

\section{Predictions\label{sec:predictions}}
We can predict some interesting values for our queueing network, but let's first look at the following problem.\\
\subsection{Minimizing the probability of a car leaving at the road of entry}
\textit{If at each intersection the probability of leaving the system is $p_\text{out}$, and the other directions are equally likely, what is the average fraction of cars that leaves from the same road as they came from?}\\\\
It is useful to introduce $x = (1-p_\text{out})/2$, so that the chance to travel to one of the two other intersections is given by $x$.
Now the chance that a car returns to its starting node for the first time after taking $n$ intersections is given by $2x^n$ for $n\geq2$. So the chance $e_1$ of leaving the system after returning to the starting node for the first time is:
$$e_1 = \left(\sum_{n=2}^{\infty}2x^n\right)\cdot p_\text{out} =\frac{2x^2}{1-x}\cdot p_\text{out}.$$
One sees that the chance to leave the system after returning to the starting node for the $m^\text{th}$ time is given by:
$$e_m = \left(\frac{2x^2}{1-x}\right)^m\cdot p_\text{out},$$
so that the total chance $p_\text{same}$ to leave the system at the place of entry is:
$$p_\text{same} = \sum_{m=0}^{\infty}\left(\frac{2x^2}{1-x}\right)^m\cdot p_\text{out}.$$
Now using $p_\text{out} = 1-2x$ and $\sum_{m=0}^{\infty}\left(\frac{2x^2}{1-x}\right)^m = \frac{x-1}{2x^2+x-1}$ we get
$$p_\text{same} = \frac{1-x}{1+x} = \frac{1+p_\text{out}}{3-p_\text{out}}.$$
It is obvious from this formula that the best we can do is set $p_\text{out}\approx 0$, so that on average $1/3$ of the cars leaves on the same road as they came from. Of course this is totally unrealistic!
\subsection{Can a traffic jam occur in such simple model?}
Defining a traffic jam quantatively is of course difficult, but a common understanding is: \textit{``A situation where vehicles are fully stopped for [extended] periods of time''}. In any case, if for any node the utilization $\rho$ is larger than one the queue at that node will keep growing, so a traffic jam would occur. This is possible in our model, but it would not be a Jackson network anymore, since these are defined to have utilizations less than one at every node.
\subsection{Predictions for the queueing network}
If we describe our intersections as M/M/1 queues we can use formula \eqref{eq:p} to obtain predictions for the average number of cars at a node\footnote{The roads do not influence the steady state behaviour as long as they have enough servers (they will only add a delay between the nodes).}.
If $q_i$ denodes the average number of cars at the $i^\text{th}$ node, then:
\begin{equation}
(q_1,\dots,q_M) = \sum_{n_i=0}^{\infty}\dots\sum_{n_M=0}^{\infty}(n_1,\dots,n_M)p_{n_1,\dots,n_M},
\label{avgql}
\end{equation}
with $p_{n_1,\dots,n_M} = \prod_{i=1}^M{\rho_i^{n_i} (1 - \rho_i)}$.\\
Here $\rho_i = \frac{\lambda_i}{\mu_i}$, where $\mu_i$ is given but $\lambda_i$ has to be determined by solving equation \eqref{eq:flow}. For our small road network the solution is: 
\[
\begin{pmatrix} \lambda_1 \\ \lambda_2 \\ \lambda_3 \end{pmatrix} =
\begin{pmatrix} 1 & p_{21} & p_{31} \\ p_{12} & 1 & p_{32} \\ p_{13} & p_{23} & 1 \end{pmatrix}^{-1}
\cdot
\begin{pmatrix}\lambda_0 p_{01}\\ \lambda_0 p_{02} \\ \lambda_0 p_{03}\end{pmatrix}
\]
Using formula \eqref{avgql} we can now predict the average number of cars at a node.\\ \\
The average queue length of a road would be close to zero under our assumptions (we want the road to act merely as a delay, so it should have enough servers to not have cars queue up for it). The average number of cars on a road can be estimated from Little's Law:
\[
\bar{w_i} = \alpha_i \bar{T_i},
\] 
where $\bar{w_i}$ is the average number of cars on the $i^\text{th}$ road, $\alpha_i$ is the mean arrival rate and $\bar{T_i}$ is the mean time a car is on the road.
So the road from node $i$ to $j$ contains on average $\lambda_i p_{ij} t_\text{road}$ cars, where $t_\text{road}$ is given by the length of the road divided by the car's speed.\\ \\
The average number of cars $\bar{n}_\text{cars}$ in the system is just the sum over the roads and intersections: $$\bar{n}_\text{cars}=\sum_{i=1}^{3}\bar{q}_i + \sum_{j=1}^{6}\bar{w}_j.$$\\
Using Little's law again, we can estimate the mean service time with $$\bar{t}_\text{service} = \frac{\bar{n}_\text{cars}}{\lambda_0}.$$

\section{A more realistic road network}
Modelling the roads and intersections as a Jackson network made the analysis much easier, but the resulting
network does not behave like a real road network in many ways. Some examples:

At a normal road, cars have different speeds, they overtake each other, the distances between them depend on their speed etcetera.
We chose to model each road as a queue with multiple servers and a constant service time\footnote{Using these roads our model does not meet the formal requirements of being a Jackson network.}. This means that multiple cars can join the
road at the same time, and that all cars have a constant speed. That is of course quite unrealistic, and a solution could be to divide
the road into small pieces, each represented by a seperate queue with finite capacity. Now the service time could be made non-constant, to simulate some range of car speeds.

In a real road network most drivers would have a destination in mind, which they try to reach in the fastest
possible way. In a Jackson network it's not possible to let the next node a car will go to
depend on its history. This will make most cars in the network have strange routes, visiting the same intersection
more than once, turning back within the system, leaving at the point of entry etcetera. In our more realistic simulation we solved this
by giving cars a destination exit and letting them always take the shortest route to the destination.

Besides these two examples above, there are many other things we did not change but can be considered.
For one, the queueing behavior at intersections will be very different than FIFO
for a real traffic light, where batches of cars belonging to a road will be let through.
Also a real traffic system will have to deal with periodic behavior, a sudden burst of
traffic when people go to work for example, instead of a steady rate. Finally the simulated
system has infinite queueing capacity while in reality roads can fill up, which would form a line
on the road leading to an intersection, interfering with its traffic flow.

\section{Simulation implementation}
What follows is a very short description of our implementation, so we recommend looking at \& executing the code for details. Numpy needs to be installed\footnote{Numpy is available for download at \url{http://www.scipy.org/Download}} in order to execute our code.\\ \\
We used the Simpy package for Python to simulate our model. In terms of the Simpy language, every road and intersection become a \texttt{Resource()}, and every car is a \texttt{Process()}. We generate cars coming from the outside world by a process called \texttt{CarGenerator()}. Upon arriving at intersection $i$, the elements of $P_{ij}$ determine the probabilities of the next destination of a car. The car process waits to be served by the traffic light by the command \texttt{yield request [\dots], traffic light}, and when it is leaving the intersection it request access to the road by \texttt{yield request [\dots], road}. Most parameters can be set, such as the length of every road, the mean processing rate of each traffic light etcetera, these are all in a class \texttt{G(lobal)}. We use various \texttt{Monitor()} instances to keep track of our simulation and the program also computes and prints predicted values (see section \ref{sec:predictions}).
\section{Results \& discussion}
We wrote our program in a pretty general way, and it uses the theory that applies to Jackson networks to make predictions. By having roads with a constant processing time, our network no longer meets the strict requirements of a Jackson network. But as explained before, as long as the roads have enough servers, they just add a delay and the predictions should still be accurate.

We can for example simulate a network with a exponentially distributed service times around one for the traffic lights, a symmetric inflow of cars from the outside world of total rate $0.3$ and roads with close to zero processing time. Set the probabilities of visiting any other or leaving the system all equal to $1/3$. See table \ref{tab:results1} for the results.
\begin{table}[!b]
\begin{tabular}{l | l}
Mean number of cars in the system & 1.26\\
\hline
Mean time in the system & 4.24\\
\hline
Average number of cars at an intersection & 0.42 -  0.42 -  0.40\\
\hline
Jackson network prediction of the above & 0.42 -  0.42 -  0.42\\
\hline
Predicted mean number of cars in system & 1.26\\
\hline
Predicted mean time in system & 4.21\\
\hline
\end{tabular}
\caption{Table showing the results of our simplest simulation. One can see the predictions that we made using the theory of section \ref{sec:predictions} are quite accurate. The simulation ran up to $t = 20 000$.\label{tab:results1}}
\end{table}
\\\\
Now consider another road network, that is a bit more complicated. Assume the traffic lights still behave in the same way, but the inflow of cars
is now asymetric, for example $(0.15,0.10,0.05)$. Let's make the road between the first and second node twice as long as the other two, and set the probability of leaving the system from the second node equal to zero (the other two nodes are equally likely to be visited next). For results see table \ref{tab:results2} and figure \ref{fig:timeinsystem}.
\begin{table}[!b]
\begin{tabular}{l | l}
Mean number of cars in the system & 2.18\\
\hline
Mean time in the system & 7.33\\
\hline
Average number of cars at an intersection &  0.86 -  0.62 -  0.66\\
\hline
Jackson network prediction of the above & 0.91 -  0.64 -  0.67\\
\hline
Predicted mean number of cars in system &  2.26\\
\hline
Predicted mean time in system & 7.54\\
\end{tabular}
\caption{Table showing the results of a more complicated simulation. One can see the predictions that we made using the theory of section \ref{sec:predictions} are still quite accurate. The simulation ran up to $t = 20 000$.\label{tab:results2}}
\end{table}

\begin{figure}
\begin{center}
\includegraphics[width=7cm]{timeinsystem-secondsim.png}
\end{center}
\caption{The distribution of the time the cars stayed in the system for the second, more complicated, simulation.
Averaging over this gives the mean shown in table \ref{tab:results2}.
\label{fig:timeinsystem}}
\end{figure}

\begin{thebibliography}{9}
\bibitem{lenin}
Lecture notes on Jackson's networks (R.B. Lenin)
\end{thebibliography}

\end{document} 